

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 14785
 * Date: 2025-07-08
 * Time: 0:03
 */

public class test {
    //汉诺塔问题
    public static long dfs(int n){
        if(n==1)
            return 1;
        return 2*dfs(n-1)+1;
    }

    public static void move(char pos1,char pos2) {
        System.out.print(pos1+"->"+pos2+" ");
    }


//    public static void hanoi(int n,char pos1,char pos2,char pos3) {
//        if(n == 1) {
//            move(pos1,pos3);//只有一个圆环，从pos1-> pos3
//            return;
//        }
//        hanoi(n-1,pos1,pos3,pos2);//移出n-1圆环 pos1->pos2
//        move(pos1,pos3);//将底盘从pos1->pos3
//        hanoi(n-1,pos2,pos1,pos3);//回收n-1圆环 pos2->pos3
//    }
    public static void hanoi(int n,char pos1,char pos2,char pos3,int[]arr) {
        if(n == 1) {
            move(pos1,pos3);//只有一个圆环，从pos1-> pos3
            arr[0]++;//计数
            return;
        }
        hanoi(n-1,pos1,pos3,pos2,arr);//移出n-1圆环 pos1->pos2
        move(pos1,pos3);//将底盘从pos1->pos3
        arr[0]++;//计数
        hanoi(n-1,pos2,pos1,pos3,arr);//回收n-1圆环 pos2->pos3
    }
    public static void main1(String[] args) {
        int[]arr={0};
        //hanoi(3,'a','b','c');
        hanoi(3,'a','b','c',arr);
        System.out.println(arr[0]);
        System.out.println(dfs(3));
    }
}
